Robust shadow detection is considered a difficult problem in computer vision and other areas requiring image interpretation. Shadows may be classified depending upon whether the shadow is moving. Consequently, methods have been developed for detecting both static and moving shadows. Moving shadow detection methods are useful for videos or image sequences while static shadow detection methods are applicable to single images. Andrea Prati, Rita Cucchiara, Ivana Mikic, Mohan M. Trivedi, “Analysis and detection of shadows in video streams: a comparative evaluation”, CVPR 2001, provide an overview of prior art moving shadow detection methods.
U.S. Pat. No. 6,349,113 for METHOD FOR DETECTING MOVING CAST SHADOWS OBJECT SEGMENTATION, issued Feb. 19, 2002 to Roland Mech et al. teach one method for identifying moving shadow regions occurring in a series of images. In the MECH et al. method, both the background and the camera are assumed to be in a fixed position relative to the images being analyzed. The MECH et al. method utilizes an analysis method known as moving cues wherein pixels from two consecutive frames are compared. This is a temporal method and finds no applicability in identifying shadow regions in single, static images.
The present invention, however, pertains only to methods for static shadow detection within a single image. While moving shadow detection may take advantage of in-motion sequences where the motion cues may be exploited to help detect shadow regions in each frame, robust shadow detection in static imagery is more challenging. Compared with moving shadow detection, there are relatively few methods reported in the literature on static shadow detection. These include Elena Salvador, Andrea Cavallaro, Touradj Ebrahimi, “Shadow identification and classification using invariant color models”, IEEE International Conference on Acoustics, Speech and Signal Processing, Vol. 3, 2001, pp. 1545-1548 (SALVADOR et al.) where an invariant color model is used to develop a shadow detection system.
Joseph M. Scanlan, Douglas M. Chabries, and Richard W. Christiansen, “A Shadow detection and removal algorithm for 2-D images”, IEEE Acoustic Speech Signal processing, 1990, pp. 2057-2060 discloses the use of a mean image to detect and remove a shadow.
Christopher Jaynes, Stephen Webb, R. Matt Steele, Michael Brown, and W. Brent Seales, “Dynamic shadow removal from front projection displays”, Visualization, 2001. VIS '01. Proceedings, pp. 175-182, 2001 address the shadow detection problem for multiview input images, but a predicted image is required for each view.
Caixia Jiang and Matthew O. Ward, “Shadow Identification”, International Conference on CVPR, 1992, pp. 606-612 teach an adaptive threshold to generate dark regions followed by vertices detection to verify shadow regions.
Graham D. Finlayson, Steven D. Hordley, and Mark S. Drew, “Removing shadows from images”, ECCV 2002, pp. 823-836, 2002 address the illumination invariant shadow removal problem, where a sequence of images of a fixed scene is required to generate a camera calibration.
Y. Weiss, “Deriving Intrinsic Images From Image Sequences”, ICCV 2001, pp. 68-75 successfully separates images into reflectance images (shadow free images) and illumination images under the assumption that those images contained same reflectance intrinsic image (i.e., they are taken from same scene), but different illumination intrinsic images (i.e., they were taken at a different time).
Gureth Funka-lea and Ruzena Bajcsy, “Combining Color and Geometry for the Active, Visual Recognition of Shadows”, ICCV 1995, pp. 203-209 (FUNKA-LEA et al.) combine color and geometry to detect shadows cast by non-point light sources.
Each of these existing methods suffers from one or more of the following problems:
1) These prior art methods are heavily dependent on brightness and illumination conditions. Most algorithms have parameters that fit only particular illumination conditions. If these algorithms are left unchanged and applied to images with different illumination conditions, the shadow detection performance is generally unacceptable.
2) These prior art methods use color information in a rather ad hoc manner. Most assume that the shadows are dark.
3) Often these shadow detection methods of the prior art fail to combine geometric information leads. This failure often results in unsatisfactory shadow detection performance when analyzing real, complex images. It is recognized that each shadow object has a geometric connection with the object generating it. Pixel level classification schemes do not take advantage of this geometric connection sufficiently, if at all.
4) Most prior art detection methods make at least some assumptions based on prior knowledge of scene geometry.
On the other hand, the method of the present invention overcomes these and other shortcomings of these known prior art methods. The inventive method makes no assumptions other than single color images that have only a single point light source (e.g., the sun) are being analyzed. To overcome the first problem of prior art methods, the inventive method adds a pre-processing step to change a red/green/blue (RGB) color space into a normalized Log RGB space, which is brightness and illumination invariant. Such a process is suggested by Graham Finlayson and Ruixia Xu, “Illuminant and Gamma Comprehensive Normalization in log RGB Space”, Pattern Recognition Letter, 24 (2003), pp. 1679-1690.
To overcome the above-identified second and third problems, the inventive method provides a two-level shadow detection algorithm. At the pixel level, the image is modeled as a reliable lattice (RL). The lattice reliability is defined by both node reliabilities and link reliabilities. The inventors have determined that shadow detection can be achieved by finding the RL having the maximum lattice reliability. At the region level, application oriented procedures which remove most possible false detected regions are applied. Since shadow detection can be considered as a special case of image segmentation, the relationship between the RL model and an MRF model such as that taught by Charles A. Bournan, “Markov Random Fields and Stochastic Image Models”, Tutorial presented at ICIP 1995 is also developed. MRF models are known to be one of the most popular models for image segmentation. For this reason, their use in shadow detection is important and also allows for possibility of extending the methods of the present invention into more general image segmentation areas. The relationships between RLs and MRFs are developed hereinbelow.